fn mulmod(a: u64, b: u64, p: u64) -> u64 {
    ((a as u128) * (b as u128) % (p as u128)) as u64
}

fn power(mut a: u64, mut b: u64, p: u64) -> u64 {
    let mut res = 1;
    while b > 0 {
        if (b & 1) == 1 {
            res = mulmod(res, a, p);
        }
        (a, b) = (mulmod(a, a, p), b >> 1);
    }
    res
}

fn break2(mut x: u64) -> (u64, u64) {
    let mut cnt = 0;
    while (x & 1) == 0 {
        x >>= 1;
        cnt += 1;
    }
    (x, cnt)
}

fn mr(n: u64) -> bool {
    if n < 2 || n % 2 == 0 {
        return n == 2;
    }
    let (d, c) = break2(n - 1);
    let arr =vec![2, 3, 7, 61, 24251, 4840261];
    for a in arr {
        if a >= n {
            continue;
        }
        if n % a == 0 {
            return false;
        }
        let mut t = power(a, d, n);
        if t == 1 || t == n-1 {
            continue; // pass
        }
        for _ in 1..c {
            t = mulmod(t, t, n);
            if t == 1 { // fail
                return false;
            }
            if t == n - 1 { // pass
                break;
            }
        }
        if t != n - 1 { // fail
            return false;
        }
    }
    true
}

fn isprime(number: u64) -> bool {
    let result = mr(number);
    result
}

pub fn min_edge_prime_num(number: u32) -> String {
    let mut prime_count = 0;
    let mut number_count = 1;
    for radix in 1.. {
        let tmp = 4 * radix * radix + 1;
        number_count += 4u64;
        prime_count += vec![
            tmp - 2 * radix,
            tmp,
            tmp + 2 * radix,
            tmp + 4 * radix,
            ].iter()
            .filter(|&number| isprime(*number))
            .count() as u64;
        // println!("{}: {}/{}", radix, prime_count, number_count);
        if prime_count * 100 < number_count * (number as u64) {
            // println!("largest value = {}", tmp + 4 * radix);
            return format!("{},{}", 2*radix+1, prime_count);
        }
    }
    unreachable!()
}
